"""
给定一个无重复元素的正整数数组candidates和一个正整数target，找出candidates中所有可以使数字和为目标数target的唯一组合。
candidates中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
对于给定的输入，保证和为target 的唯一组合数少于 150 个。

示例1：
输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]

示例2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：
输入: candidates = [2], target = 1
输出: []

示例 4：
输入: candidates = [1], target = 1
输出: [[1]]

示例 5：
输入: candidates = [1], target = 2
输出: [[1,1]]

链接：https://leetcode-cn.com/problems/Ygoe9J

"""
from mode import *


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        ans = []
        candidates.sort()
        temp = []

        def dfs(candidate, idx, target):
            if target == 0:
                ans.append(list(temp))
                return
            for i in range(idx, n):
                if candidate[i] > target:
                    break
                if i > idx and candidate[i] == candidate[i - 1]:
                    continue
                temp.append(candidate[i])
                dfs(candidate, i + 1, target - candidate[i])
                temp.pop()

        dfs(candidates, 0, target)
        return ans


if __name__ == "__main__":
    A = Solution()
    print(A.combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
